An assumption-based truth maintenance system (ATMS) is a tool for organizing a search through a "space" of alternatives. The assumption-based truth maintenance system (ATMS) was first introduced by Johan de Kleer. The de Kleer ATMS is described in a paper entitled "An Assumption-based Truth Maintenance System," which appeared in Artificial Intelligence, Vol. 28, pp. 127-162 (1986). This paper is incorporated herein by reference and made a part hereof. From the descriptions in this paper, one of ordinary skill in this art is able to construct a functional assumption-based truth maintenance system (ATMS) tool. An understanding of the basic concepts in this article is therefore necessary to appreciate the subject matter of the present invention.
In order to solve a problem in artificial intelligence, a knowledge-based system must often search through a space (or collection) of representations of alternative "states" of the problem environment. Herein a "state" is considered to be represented by a set of "assertions" which are held to be true at a particular time. An "assertion" is a data structure representing a statement or proposition in some knowledge-representation language about some aspect of the problem environment. An "assertion" does not carry a connotation of truth. That is, an "assertion" about a specified situation can either be believed or disbelieved by a given agent. It may be noted that some writers use the term "fact" or the term "node"in the sense the term "assertion" is used herein.
The selection of the set of "assertions" is based on their relevance to a particular problem. As an example, in planning a sequence of actions to achieve a goal, a planning system (which is a particular type of knowledge-based system) may search through a "space" of "states" that result from the performance of actions. On the other hand, a diagnosis system (which is another type of knowledge-based system) often searches through a "space" of alternative hypotheses about the "states" of a device that exhibits a certain behavior, e.g., faulty behavior.
Before proceeding further, reference is made to the Handbook of Artificial Intelligence, Volume I, edited by Avram Barr and Edward Feigenbaum (William A. Kaufmann, Inc., Los Altos, Calif., 1981). In particular, reference is made to pages 36 and 37 which describes the traditional notion of what is called a "context mechanism" in the prior literature. As used herein, a traditional "context mechanism" is termed a "world mechanism." Further, the term "world" as used herein is a synonymous term for the traditional term "context". The traditional notion of "context" should be distinguished from the use of the term "context" in the de Kleer paper. Reference is also made to the Handbook of Artificial Intelligence at pp. 72-76 in which is described the traditional notion of a "truth maintenance system."
It is possible to approach anew the representation and search of a "space" with each implementation of a knowledge-based system. However, it is often more convenient to provide tools and languages for constructing a knowledge-based system which permit the elimination of part of the work of designers or "knowledge engineers" by providing certain general-purpose facilities for representing and searching problem states.
Languages have been designed for use in artificial intelligence programming to render it more convenient to make the representations needed by knowledge-based systems. Two languages in particular, namely Conniver and QA4, introduced the concept of a (traditional) "context mechanism" for representing multiple "states" of a problem environment. Each "context" (world) consists of a set of "assertions" describing a state. The "context mechanisms" (world mechanisms) provided in Conniver and QA4 allow a tree of contexts to be "grown," in which each new "child" context starts out with the same assertions as its "parent," but then each "child context" may have assertions deleted and added in order to distinguish the "state" that it represents from that of its "parent". Such a tree of "contexts" (worlds) might be used, for example, to represent the intermediate "states" resulting from alternative sequences of actions. Each sequence of actions corresponds to a "path" in the tree.
Although the context mechanisms (traditional term) introduced by the languages Conniver and QA4 are quite useful for simple problems, there are several weaknesses. For example, no distinction is made in the set of assertions associated with a context (world) between those that are primitively specified and those that are derived by a deduction from primitive assertions and general knowledge of the problem domain. The user of the context mechanism must then explicitly specify not only the primitive deletions defining a new context but also deletions of derived assertions whose derivations are no longer valid in the new context. Furthermore, derivations of assertions performed in one context are not automatically transferred to non-descendant contexts in which they are also valid. Finally, the restriction to a tree-structured context graph may impose unnecessary sequential dependencies on choices in a search, which leads to inefficient chronological backtracking upon failure. (Chronological backtracking is mentioned and described in greater detail in The Handbook and Artificial Intelligence, Vol. I. In addition, the de Kleer article describes other selected problems with the chronological backtracking technique.)
Largely in response to the weaknesses of traditional context mechanisms described above, truth maintenance systems were developed. A truth maintenance system (TMS) is a tool or technique which can be used in a knowledge-based system to record derivation steps made by a problem solver as justifications linking assertions. A derivation is a set of problem solving steps each of which produces a conclusion from a given set of assertions. A TMS tool records a derivation step as a data structure called a "justification."
Traditional truth maintenance systems have several advantages. Because of the existence of justification records, derivation steps need not be repeated once they have been performed. Thus, a truth maintenance system is able to share partial results across different branches of a search space. Truth maintenance systems are also a useful and convenient tool for keeping track of contradictions among assertions which have been discovered by a problem solver, and thus they provide a basis for subsequently avoiding contradictions. Finally, justification records provide a basis for production of explanations of why assertions are to be believed.
Although truth maintenance systems provide a better means for recording dependencies among assertions than traditional context mechanisms, traditional truth maintenance systems are restricted to representing a single consistent problem state (i.e., context or world) at any single time. In addition, it is difficult to specify a transition to another context and inefficient to perform such a context switch. It is also difficult to explicitly compare distinct contexts.
The assumption-based truth maintenance system (ATMS), introduced by de Kleer, is a tool which is an advance over earlier truth maintenance systems in that the ATMS tool permits simultaneous reasoning about multiple, possibly conflicting contexts, avoiding the cost of context switching. The basic elements of the ATMS tool are "assumptions" and "assertions" (which de Kleer calls "nodes"). An assumption in the ATMS tool is an elementary stipulation which corresponds to a decision or choice. Assertions may be "justified" in terms of other assertions or in terms of assumptions. By tracing back through the justification structure, it is possible to determine the ultimate support for a derivation of an assertion as a set of assumptions. Such a set is called an "environment" for the assertion. Since an assertion may have multiple derivations, it may also have multiple environments. The set of (minimal) environments for an assertion is called its "label." Computing the labels of assertions is one to the major activities of the ATMS tool.
The basic inputs to the ATMS tool are new justifications. Such justifications cause the labels of affected assertions to be recomputed. Within the ATMS tool, there is a mechanism for denoting contradiction. This mechanism makes use of a "false" assertion. This "false" assertion is similar to a conventional assertion, may have justifications and may be associated with environments. The environments in the label of the false assertion are called "nogoods." Nogoods constitute minimal inconsistent environments. Environments which are discovered to be inconsistent, i.e., which are supersets of nogoods, are removed from the labels of assertions so that they are not used for further reasoning.
The ATMS tool, as described in the prior art, views problem solving as purely inferential. However, problems involving temporal changes or actions require some additional mechanism. Specifically, the ATMS tool does not provide the ability to delete an assertion in the transition from a parent context to a child context.